It is common in modem practice to convert analog signals to digital form for transmission. The analog signal is passed through a low-pass filter (to ensure that the signal is bandwidth limited), sampled, each sample converted to an n-bit binary word by an analog-to-digital converter, and then the bit stream is transmitted to a receiver which reconstructs the signal using a digital-to-analog converter and a low-pass filter.
Many modem digital communications systems, however, must encompass more than point-to-point digital communication. Many digital communications systems of today must also operate in networked environments which simultaneously connect a plurality of users allowing them to communicate with each other. Many of today's digital communications systems must further include the ability to transmit voice, video and data across the same transmission line. One example of such an all purpose digital communications system is the integrated services digital network (ISDN) which is currently undergoing worldwide standardization.
Asynchronous transfer mode (ATM) is a packet based communication protocol for use with an ISDN. Asymmetric Digital Subscriber Loops (ADSL) is a communications protocol defining communication across twisted pairs which may also be used on an ISDN. Discrete Multitone (DMT) was recently chosen as the standard modem for ADSL by the ANSI Standards Committee T1E1.4. Thus, any method that improves the performance or lowers the cost of a DMT system will therefore have potential widespread use in the DMT systems that will be designed over the next few years for use in ADSL and ISDN applications.
An initial operation that must take place before transmission using a DMT system is the equalization of the channel. Channel equalization is the technique of recovering transmitted signals which have been distorted by, among other things, intersymbol interference. Intersymbol interference results from various dispersion effects in the channel which broaden the pulses and cause them to interfere with one another. The Nyquist criterion, which assumes no intersymbol interference, generally cannot be satisfied unless the channel is first equalized, i.e., filtered to compensate for the channel dispersion.
In a single tone system, equalization tries to remove all intersymbol interference. In a DMT, however, channel equalization is necessary so that as much of the energy of the overall impulse response as possible is contained in a fixed number of symbol periods, called the cyclic prefix length of the DMT system. Several methods to optimally choose the equalizer in a DMT system have previously been proposed. These methods, however, are computationally complex and, as a result, require an enormous amount of computer memory and computer processing time in order to implement them.
A DMT system is a block based modulation system or modem used to transmit data across a twisted pair. A block based modulation system processes a set number of symbols in a given sequence as a group. The size of the block is constrained by system complexity considerations. For ADSL, the block size has been chosen to be 512 symbols. Because of the way in which a DMT system demodulates the signal, when a block of symbols of length N is transmitted over the channel, it must be prefixed by a block of symbols of length .nu. called the cyclic prefix. The cyclic prefix, however, is merely a copy of the last .nu. symbols of the data block and therefore contains no additional information. It is therefore desirable to make .nu. as small as possible.
In an ideal DMT system, the cyclic prefix length .nu. is constrained to be greater than the impulse response length of the channel (the length in symbol periods between the modulator and the demodulator). In most practical situations, the impulse response of the channel is too large and the size of the overall impulse response between the modulator and the demodulator must be reduced using a time domain equalizer (TEQ) so that the impulse response is zero outside of a finite region also of length .nu., called the response region.
The ideal DMT system is illustrated in FIG. 1. The system includes a modulator 10, which generates a signal output at 12 which includes data symbols of length N 14 and a cyclic prefix of length .nu. 16. The signal output at 12 then goes through a distorting channel 18 of length H. The distorted signal at 20 from the distorting channel 18 is then equalized in a finite length equalizer 22 of length M. The equalized signal at 24 is then demodulated in demodulator 24 in preparation for further processing.
In a practical DMT system, however, it is usually impossible to exactly zero out the response outside the response region using a finite length equalizer. Thus, one problem is to find a filter, w, of length M such that when the filter w is convolved with the channel, h, the response of the overall response filter, h, has most of its energy within the response region. Mathematically, the overall response filter his EQU h=h*w (EQ 1)
and we must find EQU arg.sub.w min{.parallel.b=h.parallel..sup.2 : s.t. (length (b).ltoreq..nu.)}. (EQ 2)
In (EQ 2), b is the ideal overall filter and is equivalent to the overall response filter h with the taps outside the response region set to zero. It is important to note that the ideal overall response filter b can be anything as long as it satisfies the length constraint where the length of a filter is defined as the distance between its first and last nonzero points. For example, the length of a filter with response [0, 0, 1, 0, 3, 0, 0, 0] is 3. This allows the introduction of a delay, .DELTA., if it decreases the energy in the response outside the response region.
Thus, the minimization of (EQ 2) is equivalent to minimizing the average error, or the optimization error, .epsilon..sub.k, in the system where the ideal overall response filter b includes the filter, b (the length .nu. nonzero portion of the ideal overall response filter b) with a delay .DELTA. added. The optimization error .epsilon..sub.k is thus equal to the output of the ideal overall response filter b less the output of the overall response filter h.
Methods of the prior art are based on the realization that the problem is similar to the optimization problem for decision feedback equalization (DFE), where the filter w is the feedforward filter and the filter b is the feedback filter. The only difference is that in the DMT case, the filter b does not have to be monic and causal (that is, the first tap does not have to be constrained to unity). Methods of the prior art therefore proposed the following algorithm shown which finds the optimum equalizer for a delay .DELTA. over a range .DELTA..sub.min to .DELTA..sub.max :
1. Estimate the cross correlation between the channel input x.sub.k and the channel output y.sub.k and the autocorrelation of the channel output y.sub.k. PA1 2. For delay .DELTA.=.DELTA..sub.min to .DELTA..sub.max PA1 3. Choose the minimum of all the solutions found.
a. for i=1 to .nu.
(i) constrain the ith tap of the filter b to be unity PA3 (ii) minimize .parallel.b-h.parallel..sup.2 using the DFE minimization technique
In the methods of the prior art, however, for each iteration of step 2a (ii), the formation of two new matrices and a matrix inversion must be performed. Since .nu. may be greater than thirty in practical DMT systems, this means that an enormous number of computations and data accesses must be performed for each delay .DELTA. tried.
Thus, the essential problem with methods of the prior art is that the minimization step must be performed .nu. times for each value of the delay .DELTA. tried. It is because an unconstrained minimization will produce the result filter w equal to zero and filter b equal to zero, that methods of the prior art chose to apply .nu. constraints similar to those applied in DFE optimization, i.e., forcing each tap in turn to be unity and optimizing the other taps.
What is needed is a system and method of equalizing a signal transmitted through a distorting channel which is computationally less complex than methods and systems of the prior art thus using less processor time and computer memory and being suitable for implementation using either a programmable digital signal processor, a dedicated ASIC or a general purpose digital computer.